// 给定一个区间的集合intervals，从集合中移除部分区间，使得剩下的区间互不重叠，返回需要移除区间的最小数量

// 思路：换个角度就是 求 所有区间中不重叠区间的最多个数
// 1. 转换问题：将问题转变为，当选择结束时间最早的区间后，再在剩下的时间内选出最多的区间
// 2. 贪心选择性质：每次选择时，选择结束时间最早的区间，这样选出来的区间一定是原问题最优解的区间之一
// 3. 最优子结构性质: 贪心选择当前时间最早的区间 + 剩下的时间内选出最多区间的子问题最优解,就是全局最优解

function eraseOverlapIntervals(intervals) {
    if (!intervals) {
        return 0
    }
    intervals.sort((a, b) => a[1] - b[1])
    let end_pos = intervals[0][1]
    let count = 1
    for (let i = 1; i < intervals.length; i++) {
        if (end_pos <= intervals[i][0]) {
            count += 1
            end_pos = intervals[i][1]
        }
    }
    return intervals.length - count
}

let intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]

// console.log(eraseOverlapIntervals(intervals));

function eraseOverlapIntervals2(intervals) {
    let size = intervals.length
    if (size === 0) {
        return 0
    }
    intervals.sort((a, b) => a[0] - b[0])
    let dp = new Array(size).fill(1)
    for (let i = 1; i < size; i++) {
        for (let j = 0; j < i; j++) {
            if (intervals[j][1] <= intervals[i][0]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }            
        }        
    }
    return size - Math.max(...dp)

}

console.log(eraseOverlapIntervals2(intervals));
